package com.LeeCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 合并区间
 */

public class Code056 {
    public static void main(String[] args) {

        int[][] matrix = {{1, 3}, {2, 6}, {15, 18}, {8, 10}, {19, 20}}, res;
        res = new Code056().merge1(matrix);
        System.out.println(Arrays.deepToString(res));
    }

    public int[][] merge(int[][] intervals) {

        if (intervals.length == 1) {
            return intervals;
        }

        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> res = new ArrayList<>();

        int left = 0, right = 1;
        while (left < right) {
            if (intervals[left][1] >= intervals[right][0]) { // 可以合并
                intervals[left][1] = Math.max(intervals[left][1], intervals[right][1]);
                right++;
            } else { // 无法合并新区间
                res.add(intervals[left]);
                left = right;
                right++;
            }

            if (right == intervals.length) { // 添加最后一个区间
                res.add(intervals[left]);
                break;
            }
        }

        return res.toArray(new int[res.size()][]);
    }

    public int[][] merge1(int[][] intervals) {
        // 特判
        if (intervals == null || intervals.length == 0) {
            return new int[0][];
        }

        // 找最大 end，用于确定数组大小
        int maxEnd = 0;
        for (int[] interval : intervals) {
            maxEnd = Math.max(maxEnd, interval[1]);
        }

        // 差分数组，大小为 2 * maxEnd + 2（防止越界）
        int[] diff = new int[2 * maxEnd + 2];

        // 构造差分：start*2 +=1, end*2+1 -=1
        for (int[] interval : intervals) {
            int start = interval[0];
            int end = interval[1];
            diff[start * 2]++;
            diff[end * 2 + 1]--;
        }

        // 前缀和
        int[] acc = new int[diff.length];
        acc[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            acc[i] = acc[i - 1] + diff[i];
        }

        // 遍历前缀和数组，合并连续覆盖段
        List<int[]> result = new ArrayList<>();
        Integer start = null;

        for (int i = 0; i < acc.length; i++) {
            if (acc[i] > 0) {
                if (start == null) {
                    start = i;  // 开始一个新区间
                }
            } else {
                if (start != null) {
                    // 结束当前区间：[start//2, i//2]
                    result.add(new int[]{start / 2, i / 2});
                    start = null;
                }
            }
        }

        // 转为二维数组返回
        return result.toArray(new int[0][]);
    }
}
